|
In the automata theory, a nondeterministic finite automaton with ε-moves (NFA-ε)(also known as ''NFA-λ'') is an extension of nondeterministic finite automaton(NFA), which allows a transformation to a new state without consuming any input symbols. The transitions without consuming an input symbol are called ''ε-transitions'' or ''λ-transitions''. In the state diagrams, they are usually labeled with the Greek letter ε or λ. ε-transitions provide a convenient way of modeling the systems whose current states are not precisely known. ε-transitions do not add any extra capacity of recognizing formal languages. NFA-ε's and NFAs recognize same class of formal languages, namely regular languages. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA. Since a NFA-ε can always be transformed into a NFA, the properties are also true for NFAs. ==Informal introduction== For example, let's suppose an NFA-ε contains two states, 1 and 2, and it can move to state 2 without consuming any input symbols. If it is in state 1, with the next input symbol, an ''a'', there is an ambiguity: Is the system in state 1 or state 2 before consuming the letter ''a''? Because of this ambiguity, it is more convenient to talk of ''the set of possible states'' that the system may be in. Thus, before consuming letter ''a'', the NFA-ε may be in any one of the states of the set . Equivalently, one may imagine that the NFA is in state 1 and 2 'at the same time' and this gives an informal hint of the powerset construction that translates an NFA to an equivalent DFA. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Nondeterministic finite automaton with ε-moves」の詳細全文を読む スポンサード リンク
|